package leetcode.editor.day;

import java.util.HashMap;
import java.util.Map;

// 1224. 最大相等频率
// https://leetcode.cn/problems/maximum-equal-frequency/
class MaximumEqualFrequency {
    public static void main(String[] args) {
        Solution solution = new MaximumEqualFrequency().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxEqualFreq(int[] nums) {
            Map<Integer, Integer> countMap = new HashMap<>();  // 记录数字个数
            Map<Integer, Integer> freqMap = new HashMap<>();   // 记录频率出现的次数
            int maxFreq = 0, res = 0;
            for (int i = 0; i < nums.length; i++) {
                // 原个数频率减一
                if (countMap.containsKey(nums[i]) && countMap.get(nums[i]) > 0) {
                    Integer count = countMap.get(nums[i]);
                    freqMap.put(count, freqMap.getOrDefault(count, 0) - 1);
                }

                // 个数加一
                countMap.put(nums[i], countMap.getOrDefault(nums[i], 0) + 1);

                // 更新最大频率
                maxFreq = Math.max(maxFreq, countMap.get(nums[i]));

                // 更新频率出现次数
                Integer count = countMap.get(nums[i]);
                freqMap.put(count, freqMap.getOrDefault(count, 0) + 1);

                // 判断是否符合条件
                // 一：出现的最大频率为1，随便去掉哪个数字都是满足的
                // 二：出现的最大频率的个数为1，其他都是maxFreq - 1 ，此时去掉最大频率的数可以满足（如何判断其他都是maxFreq，使用总个数判断）
                // 三：其他都是maxFreq，而频率为1的个数有1个，此时删掉频率为1的数就行
                boolean flag = maxFreq == 1
                        || freqMap.get(maxFreq) == 1 && freqMap.get(maxFreq) * maxFreq + freqMap.get(maxFreq - 1) * (maxFreq - 1) == i + 1
                        || freqMap.get(1) == 1 && freqMap.get(maxFreq) * maxFreq + 1 == i + 1;
                if (flag) {
                    res = Math.max(res, i + 1);
                }
            }

            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
